{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #望远镜中最高的海拔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAltitude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #望远镜中最高的海拔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>科技馆内有一台虚拟观景望远镜，它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 <code>heights</code> ，其中 <code>heights[i]</code> 表示对应位置的海拔高度。请找出并返回望远镜视野范围 <code>limit</code> 内，可以观测到的最高海拔值。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [14,2,27,-5,28,13,39], limit = 3\n",
    "<strong>输出：</strong>[27,27,28,28,39]\n",
    "<strong>解释：</strong>\n",
    "  滑动窗口的位置                最大值\n",
    "---------------               -----\n",
    "[14 2 27] -5 28 13 39          27\n",
    "14 [2 27 -5] 28 13 39          27\n",
    "14 2 [27 -5 28] 13 39          28\n",
    "14 2 27 [-5 28 13] 39          28\n",
    "14 2 27 -5 [28 13 39]          39</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p>你可以假设输入总是有效的，在输入数组不为空的情况下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= limit &lt;= heights.length</code></li>\n",
    "\t<li><code>-10000 &lt;= heights[i] &lt;= 10000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 239 题相同：<a href=\"https://leetcode-cn.com/problems/sliding-window-maximum/\">https://leetcode-cn.com/problems/sliding-window-maximum/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hua-dong-chuang-kou-de-zui-da-zhi-lcof](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hua-dong-chuang-kou-de-zui-da-zhi-lcof](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[14,2,27,-5,28,13,39]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        if not heights or limit==0:return heights\n",
    "        deque=collections.deque()\n",
    "        res,le=[],len(heights)\n",
    "        for i in range(limit):\n",
    "            while deque and deque[-1]<heights[i]:\n",
    "                deque.pop()\n",
    "            deque.append(heights[i])\n",
    "        res.append(deque[0])\n",
    "        for i in range(limit,le):\n",
    "            if deque[0]==heights[i-limit]:\n",
    "                deque.popleft()\n",
    "            while deque and deque[-1]<heights[i]:\n",
    "                deque.pop()\n",
    "            deque.append(heights[i])\n",
    "            res.append(deque[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        if not heights:\n",
    "            return []\n",
    "        result = []\n",
    "        i = 0\n",
    "        while i + limit <= len(heights):\n",
    "            result.append(max(heights[i:i+limit]))\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一：会超时，这道题比239题简单些，这样写不超时，但是239题这样写会超时\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "#         # base case\n",
    "#         if not heights or len(heights) < 2:\n",
    "#             return heights\n",
    "\n",
    "#         ans = []\n",
    "#         windows = deque()\n",
    "#         for i in range(len(heights)):\n",
    "#             if i < limit - 1:\n",
    "#                 windows.append(heights[i])\n",
    "#             else:\n",
    "#                 windows.append(heights[i])\n",
    "#                 ans.append(max(windows))\n",
    "#                 windows.popleft()\n",
    "        \n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 方法二：这个方法比较好，239题也不超时，跟方法一都掌握下\n",
    "# 不需要维护窗口，只需维护一个递减队列\n",
    "# class Solution:\n",
    "#     def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "#         # base case\n",
    "#         if not heights or len(heights) < 2:\n",
    "#             return heights\n",
    "        \n",
    "#         ans = []\n",
    "#         q = deque()\n",
    "#         for i in range(len(heights)):\n",
    "#             # 维护单调递减队列\n",
    "#             while q and heights[q[-1]] < heights[i]:\n",
    "#                 q.pop()\n",
    "\n",
    "#             q.append(i) # idx加入队列\n",
    "\n",
    "#             # 检查队首元素是否在窗口内\n",
    "#             while q[0] <= i-limit:\n",
    "#                 q.popleft()\n",
    "            \n",
    "#             # 最后一次检查，主要是看第一次的窗口是否形成\n",
    "#             if i+1 >= limit:\n",
    "#                 ans.append(heights[q[0]])\n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 方法三：方法二的易理解版\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        # base case\n",
    "        if not heights or len(heights) < limit:\n",
    "            return heights\n",
    "\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        # 设置首次窗口\n",
    "        for i in range(limit):\n",
    "            while q and heights[q[-1]] < heights[i]:\n",
    "                q.pop()\n",
    "            q.append(i) # 队列里之所以要存储idx，是因为后面75行要判断长度的原因\n",
    "        \n",
    "        # 开始进行第二次及以后的窗口\n",
    "        ans.append(heights[q[0]])\n",
    "        for i in range(limit, len(heights)):\n",
    "            while q and heights[q[-1]] < heights[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "            # 检查队首元素是否在窗口内\n",
    "            while q[0] <= i - limit:\n",
    "                q.popleft()\n",
    "            \n",
    "            ans.append(heights[q[0]])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        _size = len(heights)\n",
    "        next_ele = [-1 for i in range(0, _size)]\n",
    "        stack = []\n",
    "        for x in range(0, _size):\n",
    "            while stack and heights[stack[-1]] < heights[x]:\n",
    "                next_ele[stack.pop(-1)] = x\n",
    "            stack.append(x)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        if limit > 0:\n",
    "            last = -1\n",
    "            for x in range(0, _size - limit + 1):\n",
    "                idx = None\n",
    "                if last > x and last - x + 1 <= limit:\n",
    "                    idx = last\n",
    "                else:\n",
    "                    idx = x\n",
    "                while next_ele[idx] != -1 and next_ele[idx] - x + 1 <= limit:\n",
    "                    idx = next_ele[idx]\n",
    "                last = idx\n",
    "                ans.append(heights[idx])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        _size = len(heights)\n",
    "        next_ele = [-1 for i in range(0, _size)]\n",
    "        stack = []\n",
    "        for x in range(0, _size):\n",
    "            while stack and heights[stack[-1]] < heights[x]:\n",
    "                next_ele[stack.pop(-1)] = x\n",
    "            stack.append(x)\n",
    "        print(next_ele)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        if limit > 0:\n",
    "            last = -1\n",
    "            for x in range(0, _size - limit + 1):\n",
    "                idx = None\n",
    "                if last > x and last - x + 1 <= limit:\n",
    "                    idx = last\n",
    "                else:\n",
    "                    idx = x\n",
    "                while next_ele[idx] != -1 and next_ele[idx] - x + 1 <= limit:\n",
    "                    idx = next_ele[idx]\n",
    "                last = idx\n",
    "                ans.append(heights[idx])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, nums: List[int], k: int) -> List[int]:\n",
    "        freq = Counter()\n",
    "        pq = []\n",
    "        n = len(nums)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            heapq.heappush(pq, -nums[i])\n",
    "            freq[nums[i]] += 1\n",
    "            if i >= k-1:\n",
    "                ret.append(-pq[0])\n",
    "                freq[nums[i-k+1]] -= 1\n",
    "            while pq and freq[-pq[0]] == 0:\n",
    "                heapq.heappop(pq)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        if limit == 0:\n",
    "            return []\n",
    "        if limit == 1:\n",
    "            return heights\n",
    "        if limit >= len(heights):\n",
    "            return [max(heights)]\n",
    "        \n",
    "        heights = [i*(-1) for i in heights]\n",
    "\n",
    "        arr = heights[:limit]\n",
    "        res = [min(arr)]\n",
    "\n",
    "        for i in range(limit, len(heights)):\n",
    "            arr.pop(0)\n",
    "            arr.append(heights[i])\n",
    "            res.append(min(arr))\n",
    "\n",
    "        return [i*(-1) for i in res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        q=[]\n",
    "        res=[]\n",
    "        if limit==0:\n",
    "            return []\n",
    "\n",
    "        for i in range(limit):\n",
    "            heapq.heappush(q, (-heights[i],i))\n",
    "        res.append(-q[0][0])\n",
    "\n",
    "        for i in range(limit, len(heights)):\n",
    "            heapq.heappush(q, (-heights[i],i))\n",
    "            while q[0][1]<i-limit+1:\n",
    "                heapq.heappop(q)\n",
    "            res.append(-q[0][0])\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        q = [(-heights[i], i) for i in range(limit)]\n",
    "        heapq.heapify(q)\n",
    "\n",
    "        res = [-q[0][0]]\n",
    "        for i in range(limit, n):\n",
    "            heapq.heappush(q, (-heights[i], i))\n",
    "            while q[0][1] <= i - limit:\n",
    "                heapq.heappop(q)\n",
    "            res.append(-q[0][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        if len(heights) == 0:\n",
    "            return []\n",
    "        arr = []\n",
    "        index = 0\n",
    "        while index < limit:\n",
    "            arr.append(\n",
    "                (-heights[index], index)\n",
    "            )\n",
    "            index += 1\n",
    "        \n",
    "        heapq.heapify(arr)\n",
    "        res = [arr[0][0]]\n",
    "        while index < len(heights):\n",
    "            heapq.heappush(\n",
    "                arr,\n",
    "                (-heights[index], index)\n",
    "            )\n",
    "            while index - arr[0][1] >= limit:\n",
    "                heapq.heappop(arr)\n",
    "            res.append(arr[0][0])\n",
    "            index += 1\n",
    "        \n",
    "        return [-item for item in res]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:\n",
    "        if limit == 0:\n",
    "            return []\n",
    "        if limit == 1:\n",
    "            return heights\n",
    "        if limit >= len(heights):\n",
    "            return [max(heights)]\n",
    "        \n",
    "        heights = [i*(-1) for i in heights]\n",
    "\n",
    "        q = [\n",
    "            (heights[i], i) for i in range(limit)\n",
    "        ]\n",
    "        heapq.heapify(q)\n",
    "    \n",
    "        res = [q[0][0]]\n",
    "\n",
    "        for i in range(limit, len(heights)):\n",
    "            heapq.heappush(q, (heights[i], i))\n",
    "            while q[0][1] <= i - limit:\n",
    "                heapq.heappop(q)\n",
    "            res.append(q[0][0])\n",
    "\n",
    "        return [i*(-1) for i in res]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
